package exercises.newcoder.solution;

/**
 * <a href="https://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f?tpId=188&&tqId=38549&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking">
 * NC128 接雨水问题</a>
 * <br/>
 * <img src="https://uploadfiles.nowcoder.com/images/20210416/999991351_1618541247169/26A2E295DEE51749C45B5E8DD671E879"
 *     alt="题目图示" />
 * @author or2
 * @Description 给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * @create 2021年08月31日 时间: 20:36
 */
public class MaxWater {
    /**
     * max water
     *
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater(int[] arr) {
        if (arr.length == 0) {
            return 0;
        }
//        注意题目的返回类型
        long ans = 0;

        int left = 0;
        int boundL = arr[left];
        int right = arr.length - 1;
        int boundR = arr[right];

        while (left < right) {
            if (arr[left] < arr[right]) {
                left++;
                if (arr[left] < boundL) {
                    ans += boundL - arr[left];
                } else {
                    boundL = arr[left];
                }
            } else {
                right--;
                if (arr[right] < boundR) {
                    ans += boundR - arr[right];
                } else {
                    boundR = arr[right];
                }
            }
        }

        return ans;
    }
}
